﻿// 0923train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <queue>

using namespace std;

/*
周末小明准备去爬山锻炼，0代表平地，山的高度使用1到9来表示
小明每次爬山或下山高度只能相差k及k以内，每次只能上下左右一个方向上移动一格，
小明从左上角(0,0)位置出发

输入描述
第一行输入m n k(空格分隔)
代表 m*n 的二维山地图，k为小明每次爬山或下山高度差的最大值
然后接下来输入山地图，一共 m行n列，均以空格分隔

输出描述
请问小明能爬到的最高峰多高，到该最高峰的最短步数，输出以空格分隔。
同高度的山峰输出较短步数。
如果没有可以爬的山峰，则高度和步数都返回0

示例1
5 4 1
0 1 2 0
1 0 0 0
1 0 1 2
1 3 1 0
0 0 0 9
输出
2 2

根据山地图可知，能爬到的最高峰在(0,2)位置，高度为2
最短路径为(0,0)->(0,1)->(0,2)，最短步数为2
 */
class Solution01
{
public:
    void bfs(vector<vector<int>>& grid, 
        vector<vector<bool>>&checked,
        deque<vector<int>>&bfs_queue
    )
    {
        while (!bfs_queue.empty())
        {
            curr_step += 1;
            int q_size = bfs_queue.size();

            for (int i = 0; i < q_size; i++)
            {
                vector<int>top_node = bfs_queue.front();
                bfs_queue.pop_front();
                int top_height = grid[top_node[0]][top_node[1]];
                if (top_height>max_height)
                {
                    max_height = top_height;
                    res_step = curr_step;
                }

                for (auto&dir_v:DirectionGrid)
                {
                    int curr_r = top_node[0] + dir_v[0];
                    int curr_c = top_node[1] + dir_v[1];

                    bool is_curr_r = curr_r >= 0 && curr_r < row_size_;
                    bool is_curr_c = curr_c >= 0 && curr_c < col_size_;

                    if (!is_curr_r || !is_curr_c) continue;

                    bool is_visited = checked[curr_r][curr_c];
                    int curr_height = grid[curr_r][curr_c];
                    bool is_available = abs(top_height - curr_height)<=limit_;

                    if (!is_visited && is_available)
                    {
                        bfs_queue.push_back({ curr_r,curr_c });
                        //标为已访问
                        checked[curr_r][curr_c] = true;
                    }

                    //dir_v---
                }


                //for
            }

            //while---
        }
        //bfs---
    }

    Solution01(vector<vector<int>>&grid, int row_size, int col_size, int limit)
    {
        //未越界，可到达，符合要求（高度差k以内）
        row_size_ = row_size;
        col_size_ = col_size;
        limit_ = limit;

        vector<vector<bool>>checked(row_size_, vector<bool>(col_size_));

        deque<vector<int>>bfs_queue;
        //初始节点入队
        bfs_queue.push_back({ 0,0 });
        checked[0][0] = true;
        bfs(grid, checked, bfs_queue);

        if (res_step==-1)
        {
            cout << 0 << ' ' << 0;
            return;
        }
        cout << res_step << ' ' << max_height;

	    //Solution01
    }
private:
    int row_size_ = 0, col_size_ = 0, limit_=0;
    int curr_step = -1, res_step=-1, max_height = 0;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};


string longestPalindrome(string s) {
    if (s.size() <= 1) return s;

    int s_size = s.size();
    int pos=0, max_length = 1;
    vector<vector<bool>>dynamic_v(s_size, vector<bool>(s_size,false));
    for (int i=0; i<s_size; i++)
    {
        dynamic_v[i][i] = true;//单个字符构成回文串
    }

    for (int len=2; len<=s_size; len++)
    {
	    for (int left=0; left+len-1<s_size; left++)
	    {
            int right = left + len-1;
            if (s[left]!=s[right])
            {
                //不相等，不可能构成回文串
                dynamic_v[left][right] = false;
                continue;
            }
            //相等
            if (len <= 3)
            {
                dynamic_v[left][right] = true;
            }
            else
            {
                dynamic_v[left][right] = dynamic_v[left + 1][right - 1];
            }

            if (dynamic_v[left][right] && len>max_length)
            {
                pos = left;
                max_length = len;
            }

            //for---
	    }
        //for---
    }
    
    string result = s.substr(pos, max_length);
    return result;
    //longestPalindrome
}

/*
 网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透
 在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物
- array[m][n] 的二维数组代表网格地图，
- array[i][j] = 0 代表 i 行 j 列是空旷位置;
- array[i][j] = x (x 为正整数)代表 i 行 j 列是信号源，信号强度是 x;
- array[i][j] = -1 代表 i 行 j 列是阻隔物
- 信号源只有 1 个，阻隔物可能有 0 个或 多 个
- 网络信号衰减是上下左右相邻的网格衰减 1
- 现要求输出对应位置的网络信号值

输入
输入为三行：
第一行为 m、n，代表输入是一个 m × n的数组

第二行是一串 m × n 个用空格分隔的整数
每连续 n 个数代表一行，再往后 n 个代表下一行，以此类推
对应的值代表对应的网格是空矿位置，还是信号源，还是阻隔物

第三行是 i、j，代表需要计算 array[i][j] 的网络信号值
注意:此处i和j均从 0 开始，即第一行 i为 0

输入
6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4
输出
2

 */
class Solution02
{
public:
    void bfs(
        vector<vector<int>>& grid,
        vector<vector<bool>>&checked,
        deque<vector<int>>&bfs_queue
        )
    {
        while (!bfs_queue.empty())
        {
            remain_step--;

            int q_size = bfs_queue.size();

            for (int i=0; i<q_size; i++)
            {
                vector<int>top_node = bfs_queue.front();
                bfs_queue.pop_front();

                if (top_node[0]==target_v_[0] && top_node[1] == target_v_[1])
                {
                    is_find = true;
                    break;
                }

                for (auto&dir_v:DirectionGrid)
                {
                    int row = top_node[0] + dir_v[0];
                    int col = top_node[1] + dir_v[1];

                    bool is_row = row >= 0 && row < row_size;
                    bool is_col = col >= 0 && col < col_size;

                    if (!is_row || !is_col) continue;

                    bool is_visited = checked[row][col];
                    bool is_available = grid[row][col] == 0;

                    if (!is_visited && is_available)
                    {
                        bfs_queue.push_back({ row, col });
                        //标为已访问
                        checked[row][col] = true;
                        //
                    }

                    //dir_v
                }


                //q_size
            }

            //找到终点
            if (is_find) break;

            //while
        }

        //bfs
    }


    Solution02(vector<vector<int>>&grid,
        vector<int>&size_v, vector<int>&start_v,vector<int>&target_v
    )
    {
        //信号源只有 1 个
        row_size = size_v[0]; col_size = size_v[1];
        start_v_ = start_v;
        target_v_ = target_v;

        vector<vector<bool>>checked(row_size, vector<bool>(col_size,false));

        deque<vector<int>>bfs_queue;
        //起点入队
        int start_val = grid[start_v_[0]][start_v_[1]];
        remain_step = start_val + 1;
        bfs_queue.push_back(start_v_);
        //标为已访问
    	checked[start_v_[0]][start_v_[1]] = true;

        bfs(grid, checked, bfs_queue);

        if (!is_find)
        {
            cout << 0;
            return;
        }

        cout << remain_step;
	    //Solution02
    }
private:
    bool is_find = false;
    int remain_step = 0;
    vector<int>start_v_;
    vector<int>target_v_;
    int row_size = 0, col_size = 0;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};



/*
 假设将火星待改造的区域为 row * column 的网格
 每个网格有 3 个值，宜居区、可改造区、死亡区，使用 YES、NO、NA 代替：
- YES 表示该网格已经完成大气改造；1
- NO 表示该网格未进行改造，后期可进行改造；0
- NA 表示死亡区，不作为判断是否改造完成的宜居，无法穿过；-1
初始化下，该区域可能存在多个宜居区，
并且每个宜居区能同时在每个太阳日单位向上下左右四个方向的相邻格子进行扩散，
自动将 4 个方向相邻的真空区改造成宜居区；
请计算这个待改造区域的网格中，可改造区是否能全部变成宜居区，
如果可以，则返回改造的太阳日天数，不可以则返回-1。

输入
YES YES NO
NO NO NO
NA NO YES

输出
可改造区是否能全部变成1，如果可以，则返回改造的太阳日天数，不可以则返回-1

输入
YES YES NO
NO NO NO
YES NO NO
输出
2
 */
class Solution03
{
public:
    void bfs(
        vector<vector<int>>& grid,
        vector<vector<bool>>&checked,
        deque<vector<int>>&bfs_queue
        )
    {
        while (!bfs_queue.empty())
        {
            need_step++;

            int q_size = bfs_queue.size();
            for (int i=0; i<q_size; i++)
            {
                vector<int>top_node = bfs_queue.front();
                bfs_queue.pop_front();

                for (auto&dir_v:DirectionGrid)
                {
                    int row = top_node[0] + dir_v[0];
                    int col = top_node[1] + dir_v[1];

                    bool is_row = row >= 0 && row < row_size_;
                    bool is_col = col >= 0 && col < col_size_;

                    if (!is_row || !is_col) continue;

                    bool is_visited = checked[row][col];
                    bool is_available = grid[row][col] == 0;

                    if (!is_visited&&is_available)
                    {
	                    //找到待改造
                        target_count_--;
                        //入队
                        bfs_queue.push_back({ row,col });
                        //标为已访问
                        checked[row][col] = true;
                    }


                    //for---
                }

	            
            }
	        //while
        }

	    //bfs
    }

    Solution03(vector<vector<int>>&grid)
    {
        if (grid.empty()) return;

        row_size_ = grid.size();
    	col_size_ = grid[0].size();

        vector<vector<bool>>checked(row_size_, vector<bool>(col_size_));

        deque<vector<int>>bfs_queue;

        for (int r=0; r<row_size_; r++)
        {
            for (int c=0; c<col_size_; c++)
            {
                //寻找起点
                if (grid[r][c]==1)
                {
                    bfs_queue.push_back({ r,c });
                    //标为已访问
                    checked[r][c] = true;
                }
                else if (grid[r][c]==0)
                {
                    //统计待改造数量
                    target_count_++;
                }
                //for---
            }

	        //for---
        }

        bfs(grid, checked, bfs_queue);

        if (target_count_!=0)
        {
            //不可以则返回-1
            cout << -1;
            return;
        }
        cout << need_step;

	    //Solution03
    }
private:
    int need_step = -1;
    int row_size_ = 0, col_size_ = 0;
    int target_count_ = 0;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};


/*
 题目
一天一只顽猴想要从山脚爬到山顶，途中经过一个有 n 个台阶的阶梯，
每一次只跳 1 步或 3 步。试问猴子通过这个阶梯有多少种不同的跳跃方式

输入
输入只有一个数 n， 0 <= n <= 50，代表此阶梯有多个台阶

输出描述
一个整数，表示有多少种跳跃方式

输入
50
输出
122106097
 */
class Solution04
{
public:
    Solution04(int num)
    {
        vector<long long>dynamic_v(num + 1);

        dynamic_v[0] = 1;
        dynamic_v[1] = 1;
        dynamic_v[2] = 1;

        for (int i=3; i<=num; i++)
        {
            dynamic_v[i] = dynamic_v[i - 1] + dynamic_v[i - 3];
        }

        cout << dynamic_v[num];

        //Solution04
    }
};


/*
 现在有 n 个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖）
 其次服务自身启动加载会消耗一些时间
给你一个 nxn 的二维矩阵 useTime，
其中 useTime[i][i] = 10 表示服务 i 自身启动加载需要消耗 10s，
useTime[i][j] = 1 表示服务 i 启动依赖服务 j 启动完成，
useTime[i][k] = 0，表示服务 i 启动不依赖服务 k。
存在0 <= i，j，k < n。

服务之间启动没有循环依赖（不会出现环），
若想对任意一个服务 i 进行集成测试（服务 i 自身也需要加载），求最少需要等待多少时间

输入描述
第一行输入服务总量 n，之后的 n 行表示服务启动的依赖关系以及自身启动加载耗时
最后输入 k 表示计算需要等待多少时间后可以对服务 k 进行集成测试

输出描述
最少需要等待多少时间(s)后可以对服务 k 进行集成测试

输入
3
5 0 0
1 5 0
0 1 5
3
输出
15
服务3 启动依赖服务2，服务 2 启动依赖服务 1，
由于服务 1,2,3 自身加载需要消耗 5s，所以 5+5+5=15，
需等待 15s 后可以对服务 3 进行集成测试
 */
class Solution05
{
public:
    void initData(vector<vector<int>>& grid)
    {
        for (int i = 0; i < g_size_; i++)
        {
            for (int j = 0; j < g_size_; j++)
            {
                if (i==j)
                {
                    node_val_map[i] = grid[i][i];
                }

                if (i!=j && grid[i][j] == 1)
                {
                    int start_node = j;
                    int arrive_node = i;

                    linked_map[start_node].push_back(arrive_node);
                    indegree_map[start_node] += 0;
                    indegree_map[arrive_node] += 1;
                }

                //for---
            }
            //for---
        }
        //initData
    }

    Solution05(vector<vector<int>>&grid, int g_size, int search_i)
    {
        //linked_map,indegree_map,bfs_queue
        //useTime[i][j] = 1 表示服务 i 启动依赖服务 j 启动完成
        //j->i, start_node=j, arrive_node=i
        g_size_ = g_size;
        initData(grid);

        //入度为0的点入队
        deque<int>bfs_queue;
        for (auto&item:indegree_map)
        {
            int node_i = item.first;
            if (item.second==0)
            {
                int cost = node_val_map.at(node_i);
                if (node_i==search_i)
                {
                    cout << cost;
                    return;
                }
                //更新节点当前开销
                cost_map[node_i] = cost;
                bfs_queue.push_back(node_i);
            }
        }

        while (!bfs_queue.empty())
        {
            int top_node = bfs_queue.front();
            bfs_queue.pop_front();
            int top_cost = cost_map[top_node];

            if (linked_map.count(top_node) == 0) continue;

            for (auto&next_i:linked_map.at(top_node))
            {
                indegree_map[next_i]--;
                int next_cost = top_cost + node_val_map[next_i];
                //取决于耗时最长的子节点
                cost_map[next_i] = max(next_cost, cost_map[next_i]);

                //入度为0，入队
                if (indegree_map[next_i]==0)
                {
                    bfs_queue.push_back(next_i);
                }
            }

	        //while
        }

        cout << cost_map[search_i];
	    //Solution05
    }
private:
    int g_size_ = 0;
    int result = INT_MAX;
    unordered_map<int, vector<int>>linked_map;
    unordered_map<int, int>indegree_map;
    unordered_map<int, int>cost_map;
    unordered_map<int, int>node_val_map;
};


void solve(vector<int>& num_vec)
{
    vector<int>result;
    for (auto& num : num_vec)
    {
        int curr_res = num / 3;
        int remain = num / 3 + num % 3;
        while (remain >= 3)
        {
            curr_res += remain / 3;
            remain = remain / 3 + remain % 3;
        }
        if (remain == 2) curr_res += 1;
        result.push_back(curr_res);
    }

    int result_size = result.size();
    for (int i = 0; i < result_size; i++)
    {
        cout << result[i];
        if (i != result_size - 1)
        {
            cout << '\n';
        }
    }

}

int main()
{
	{
        string input;
        vector<int>num_vec;
        while (getline(cin, input))
        {
            if (input == "0")break;
            num_vec.push_back(stoi(input));
        }
        solve(num_vec);
        return 0;
	}
	{
/*
3
5 0 0
1 5 0
0 1 5
3
*/
        int g_size;
        cin >> g_size;

        vector<vector<int>>grid(g_size, vector<int>(g_size));

        for (int r=0; r<g_size; r++)
        {
	        for (int c=0; c<g_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }
        int search_i;
        cin >> search_i;

        Solution05 solu(grid, g_size, search_i-1);

        return 0;
	}
	{
        int num;
        cin >> num;

        Solution04 solu(num);

        return 0;
	}
	{
        vector<vector<int>>grid;

        string input;
        while (getline(cin, input))
        {
            if (input.empty()) break;
            vector<int>item_v;
            stringstream oh_sstream(input);
            string token;
            while (oh_sstream >> token)
            {
                if (token=="YES")
                {
                    item_v.push_back(1);
                }
                else if (token=="NO")
                {
                    item_v.push_back(0);
                }
                else
                {
                    item_v.push_back(-1);
                }

            }
            grid.push_back(item_v);

        }

        Solution03 solu(grid);


        return 0;
	}
	{
        int row_size, col_size;
        cin >> row_size >> col_size;

        vector<int>size_v = { row_size, col_size };

        vector<int>start_v;
        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                cin >> grid[r][c];

                if (grid[r][c]>0)
                {
                    start_v = { r,c };
                }

                //for---
	        }
            //for---
        }

        vector<int>target_v(2);
        cin >> target_v[0] >> target_v[1];

        Solution02 solu(grid, size_v, start_v, target_v);

        return 0;
	}
	{
        string s = "bb";
        cout << longestPalindrome(s);

        return 0;
	}
/*
5 4 1
0 1 2 0
1 0 0 0
1 0 1 2
1 3 1 0
0 0 0 9
*/
    int row_size, col_size, limit;
    cin >> row_size >> col_size >> limit;

    vector<vector<int>>grid(row_size, vector<int>(col_size));

    for (int r=0; r<row_size; r++)
    {
	    for (int c=0; c<col_size; c++)
	    {
            cin >> grid[r][c];
	    }
    }
    Solution01 solu(grid, row_size, col_size, limit);

    //main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
